//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复
//的三元组。 
//
// 注意：答案中不可以包含重复的三元组。 
//
// 
//
// 示例： 
//
// 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
//  [-1, 0, 1],
//  [-1, -1, 2]
//]
// 
// Related Topics 数组 双指针 
// 👍 2808 👎 0


package com.yun.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    public static void main(String[] args) {
        Solution solution = new ThreeSum().new Solution();
        System.out.println(solution.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            // 三数之和
            List<List<Integer>> rs = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                // 过半就停止
                if (nums[i] > 0) {
                    break;
                }
                // 跳过第一个元素重复的情况，否则会重复
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
                // 当前位置在i
                // !!!!!! 已经遍历过的不需要再遍历，所以不用每次都从0开始遍历
                int left = i + 1;
                int right = nums.length - 1;
                // 左指针元素+右指针元素 = - i位置元素，和就是0;
                while (left < right) {
                    // 这里不用跳过，其他两个地方去重，还有不是每次都从0开始遍历，这里不存在重复;
//                    if (left == i) {
//                        left++;
//                        continue;
//                    }
//                    if (right == i) {
//                        right--;
//                        continue;
//                    }
                    int sum = nums[left] + nums[right] + nums[i];
                    if (sum == 0) {
                        rs.add(genList(nums[i], nums[left], nums[right]));
                        // 如何跳过？？？
                        // 去重，跳过
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        left++;
                        right--;
                    } else if (sum > 0) {
                        right--;
                    } else if (sum < 0) {
                        left++;
                    }
                }
            }
            return rs;
        }

        public ArrayList<Integer> genList(int a, int b, int c) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(a);
            list.add(b);
            list.add(c);
            return list;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}